package strings;

/**
 * @author pengfei.hpf
 * @date 2020/3/12
 * @verdion 1.0.0
 * 1071. 字符串的最大公因子
 * 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
 *
 * 返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
 *
 *
 *
 * 示例 1：
 *
 * 输入：str1 = "ABCABC", str2 = "ABC"
 * 输出："ABC"
 * 示例 2：
 *
 * 输入：str1 = "ABABAB", str2 = "ABAB"
 * 输出："AB"
 * 示例 3：
 *
 * 输入：str1 = "LEET", str2 = "CODE"
 * 输出：""
 *
 *
 * 提示：
 *
 * 1 <= str1.length <= 1000
 * 1 <= str2.length <= 1000
 * str1[i] 和 str2[i] 为大写英文字母
 */
public class GcdOfStrings {
    public String gcdOfStrings(String str1, String str2) {
        if(str1 == null || str2 == null){
            return "";
        }

        String res = "";
        int len1 = str1.length();
        int len2 = str2.length();
        if(len1  >  len2){
            res =  str1.substring(len2, len1);
            return gcdOfStrings(res, str2);
        } else if (len1 == len2){
            if(str1.equals(str2)){
                return str1;
            } else {
                return "";
            }
        } else {
            res = str2.substring(len1, len2);
            return gcdOfStrings(res, str1);
        }
    }

    public static void main(String[] args){
        System.out.println(new GcdOfStrings().gcdOfStrings("ABCABC", "ABC"));
    }
}
